//链表中的两数相加
class Solution {
public:
    ListNode* reverseList(ListNode* head)
    {
        if(!head) return nullptr;
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur->next)
        {
            ListNode*tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
        cur->next=pre;
        return cur;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode* head1= reverseList(l1);
        ListNode* head2= reverseList(l2);
        int carry=0;

        ListNode* newList=new ListNode(-1);
        ListNode* cur=newList;
        while(head1 || head2 ||carry)
        {
            int num1=head1!=nullptr?head1->val:0;
            int num2=head2!=nullptr?head2->val:0;
            int sum=num1+num2+carry;
            carry=sum/10;
            cur->next=new ListNode(sum%10);
            cur=cur->next;
            if(head1) head1=head1->next;
            if(head2) head2=head2->next;
        }
        return reverseList(newList->next);
    }
};
//两个链表的第一个重合节点
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        int cntA=0,cntB=0;
        ListNode* pa=headA;
        ListNode* pb=headB;
        while(pa)
        {
            pa=pa->next;
            cntA++;
        }
        while(pb)
        {
            pb=pb->next;
            cntB++;
        }
        if(pa!=pb) return nullptr;
        if(cntA>cntB)
        {
            //让pa是短的那个
            pa=headB;
            pb=headA;
        }
        else
        {
            pa=headA;
            pb=headB;
        }
        int tmp=abs(cntA-cntB);
        while(tmp--)
        {
            pb=pb->next;
        }
        while(pa!=pb)
        {
            pa=pa->next;
            pb=pb->next;
        }
        return pa;
    }
};
//删除链表的倒数第n个结点
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        ListNode* phead=new ListNode(-1);
        phead->next=head;
        ListNode*cur=phead;
        ListNode*del=phead;
        ListNode*pre=phead;
        ListNode*next=phead;
        while(--n)
        {
            cur=cur->next;
        }
        while(cur->next)
        {
            cur=cur->next;
            pre=del;
            del=del->next;
        }
        next=del->next;
        pre->next=next; 
        return phead->next;
    }
};
//回文子串的个数
class Solution {
public:
    //思路：纯暴力 挨个看
    int countSubstrings(string s) 
    {
        int res=0;
        for(int i=0;i<s.size();i++)
        {
            res+=substrings(s,i,i);
            res+=substrings(s,i,i+1);
        }
        return res;
    }
    int substrings(string& s,int l,int r)
    {
        int res=0;
        while(l>=0 && r<s.size())
        {
            if(s[l]==s[r])
            {
                res++;
                l--,r++;
            }
            else
            {
                break;
            }
        }
        return res;
    }
};
//最多删除一个字符得到回文
class Solution {
public:
    bool validPalindrome(string s) 
    {
        int l=0;
        int r=s.size()-1;
        while(l<r)
        {
            if(s[l]!=s[r])
            {
                return skip(s,l+1,r) || skip(s,l,r-1);
            }
            l++,r--;
        }
        return true;
    }
    bool skip(string& s, int l,int r)
    {
        while(l<r)
        {
            if(s[l]!=s[r]) return false;
            l++,r--;
        }
        return true;
    }
};

//二维子矩阵的和
class NumMatrix {
public:
    vector<vector<int>> sums;
    NumMatrix(vector<vector<int>>& matrix) 
    {
        int m = matrix.size();
        if (m > 0) 
        {
            int n = matrix[0].size();
            sums.resize(m, vector<int>(n + 1));
            for (int i = 0; i < m; i++) 
            {
                for (int j = 0; j < n; j++) 
                {
                    sums[i][j + 1] = sums[i][j] + matrix[i][j];
                }
            }
        }
    }
    int sumRegion(int row1, int col1, int row2, int col2) 
    {
        int sum = 0;
        for (int i = row1; i <= row2; i++) 
        {
            sum += sums[i][col2 + 1] - sums[i][col1];
        }
        return sum;
    }
};
//左右两边子数组的和相等

class Solution {
public:
    int pivotIndex(vector<int>& nums) 
    {
        //前缀和
        // 整个数组的和 -2*sum[i-1] + nums[i]=0
        int sum=0;
        int res=-1;
        for(auto e:nums) sum+=e;
        
        for(int i=0,tmp=0;i<nums.size();i++)
        {
            if(2*tmp +nums[i]==sum)
            {
                res=i;
                break;
            }
            tmp+=nums[i];
        }
        return res;
    }
};
